排序演算法在程式中是非常重要的以下會先來介紹三個基本的排序演算法

• Bubble sort
• Insertion sort
• Selection sort

Bubble Sort Big(n^2)

BubbleSort.gif

let array = [3,5,1,0,-1]

function bubbleSort(arr){
    let temp = []
    for(let i = 0; i <= arr.length-1; i++){
        for(let j = 0; j <= arr.length-1; j++){
            if(arr[j-1] > arr[j]){ //對比前項若比後項大
                temp = arr[j] //空陣列存小的
                arr[j] = arr[j-1] //把大的丟給正確位置
                arr[j-1] = temp //再把小的傳給[j-1]
            }
        }
    }return arr
}
console.log(bubbleSort(array)) //[ -1, 0, 1, 3, 5 ]

Insertion Sort BigO(n^2)

InsertSort.gif

-在排序過程中,Insertion sort must sorted

let array = [3,5,1,0,-1]

function InsertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let key = arr[i] //arr[i-1] sorted 所以要用arr[i] compare
        let j = i - 1 //j == 0
        
        while(j >= 0 && arr[j] > key){  //逐一比對是否前項比後項大
            arr[j + 1] = arr[j] //這邊使用了把每項index往前推
            j-- //--再往後比對
        }
        arr[j + 1] = key //最後空出的空間塞入key的數值
        console.log(arr)
    } 
    return arr 
}

console.log(InsertionSort(array))
/*
[ 3, 5, 1, 0, -1 ]
[ 1, 3, 5, 0, -1 ]
[ 0, 1, 3, 5, -1 ]
[ -1, 0, 1, 3, 5 ]
[ -1, 0, 1, 3, 5 ]
*/

Selection Sort BigO(n^2)

SelecionSort

let array = [3,5,1,0,-1]

function SelectionSort(arr){
    for(let i = 0; i < arr.length; i++){
        let minIndex = i
        let temp  = []
        for(let j = i; j < arr.length; j++){
            if(arr[minIndex] > arr[j]){
                minIndex = j
            }
        }
        temp = arr[minIndex] //save minIndex
        arr[minIndex] = arr[i]  //swap
        arr[i] = temp //root index = minIndex
    }
    return arr
}
console.log(SelectionSort(array))//[ -1, 0, 1, 3, 5 ]